这道题没有想象中的那么难,只不过板子P4718 【模板】Pollard-Rho算法是黑的(为什么这道题是紫的)
既然题目保证为两质数乘积。我们可以用
求出。
然后跟着题目一步步模拟,计算
然后根据计算(我用的扩欧)。
最后,用快速幂求出
因为数据范围很大,我用的是__int128,注意它不能用标准输入输出,要手写读优输优。
#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
#define int __int128
void Read( int &x ) {
x = 0;int f = 1;
char s = getchar( );
while( s < '0' || s > '9' ) {
if( s == '-' ) f = -1;
s = getchar( );
}
while( '0' <= s && s <= '9' ) {
x = x * 10 + s - '0';
s = getchar( );
}
x *= f;
}
void Write( int x ) {
if( x < 0 ) {
x = -x;
putchar('-');
}
if( x >= 10 )
Write( x / 10 );
putchar( x % 10 + '0' );
}
int Exgcd( int a , int b , int &x , int &y ) {
if( !b ) {
x = 1 , y = 0;
return a;
}
else {
int r = Exgcd( b , a % b , y , x );
y -= x * ( a / b );
return r;
}
}
int Gcd( int x , int y ) {
return y == 0 ? x : Gcd( y , x % y );
}
int Abs( int x ) {
return x >= 0 ? x : -x;
}
int f( int x , int a , int Mod ) {
return ( x * x + a ) % Mod;
}
int Quick_pow( int x , int po , int Mod ) {
int Ans = 1;
while( po ) {
if( po % 2 )
Ans = Ans * x % Mod;
x = x * x % Mod;
po /= 2;
}
return Ans;
}
int Inv( int x , int Mod ) {
int u , v;
Exgcd( x , Mod , u , v );
return ( u % Mod + Mod ) % Mod;
}
int Pollard_rho( int n ) {
int r = rand( ) % ( n - 1 ) + 1;
int a = f( 0 , r , n ) , b = f( f( 0 , r , n ) , r , n );
while( b != a ) {
int p = Gcd( Abs( b - a ) , n );
if( p > 1 ) return p;
a = f( a , r , n ) , b = f( f( b , r , n ) , r , n );
}
return n;
}
int N , e , c , p , q , r , d , n;
signed main( ) {
srand( 20060204 );
Read( e ) , Read( N ) , Read( c );
p = Pollard_rho( N ) , q = N / p;
r = ( p - 1 ) * ( q - 1 );
d = Inv( e , r );
n = Quick_pow( c , d , N );
/*Write( d ) , putchar('\n');
Write( n ) , putchar('\n');
Write( p ) , putchar('\n');
Write( q ) , putchar('\n');
Write( r ) , putchar('\n'); */
Write( d ) , putchar(' ') , Write( n );
return 0;
}